package F.树;

import java.util.LinkedList;
import java.util.Queue;

public class _111_二叉树的最小深度 {

    /**
     * 自解：深度优先遍历--但是无法判断当前是不是叶子节点
     * 代码ac不出 题解
     * 理解递归终止条件：
     * 叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
     * 当 root 节点左右孩子都为空时，返回 1
     * 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
     * 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值
     *

     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {


        if (root == null){
            return 0;
        }

        if (root.left == null && root.right ==null){
            return 1;
        }

        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (root.left == null || root.right == null){
            return left+right+1;//只要有一个为空 那么left或者right至少一个是0
        }
        //均不为空
        return Math.min(left,right) + 1;
    }

    /**
     * 自解：层次遍历 用队列 如果左右指针均为0 就可以直接返回深度
     *
     */
    public int minDepth1(TreeNode root) {

        if (root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);
        int len=0;
        while (!queue.isEmpty()){
            int node = queue.size();
            while (node >0){
                root = queue.poll();
                if (root.left == null && root.right==null){
                    return len+1;
                }

                if (root.left!= null){
                    queue.add(root.left);
                }
                if (root.right!= null){
                    queue.add(root.right);
                }
                node--;
            }
            len++;

        }

        return len;
    }

    }
